1. Field of the Invention
The present invention relates generally to the field of pattern recognition. More specifically, the present invention relates to a system, method and apparatus for pattern or symbol recognition usable in real-time applications.
2. Background Art
There are a number of applications for, and approaches to, pattern recognition. For example, neural networks can be used for character recognition. But high-volume off-the-shelf semiconductor devices for neural networks are not available. Therefore, implementations that employ neural networks can be relatively expensive and they carry an inherent risk that the parts employed might become obsolete. Also, because of compromises that are typically made to neural network devices in order to lower their cost, they may not meet the performance requirements for some real-time applications. Similarly, Digital Signal Processors (DSP""s) can also be used for pattern recognition (e.g., with correlation operations performed in either the time or the frequency domain). But DSP""s can also be expensive and may not achieve the performance level required by some real-time applications. Thus, it would be useful to have an alternate approach to pattern recognition that can achieve high performance at a relatively low-cost without significant risk of parts obsolescence.
Many display systems employ cathode ray tubes (CRT""s), but new CRT""s are not always available to repair or replace these display systems. Therefore, a demand exists to replace these displays with newly designed display systems that utilize flat-panel display technology, such as liquid crystal display (LCD) technology. But the electrical interface to existing CRT-based displays is often incompatible with the requirements of LCD-based displays because of the differences between these two technologies. The primary incompatibility of these two technologies is in the way that the individual pixels of each display type are selected for illumination. LCD technology employs a mechanism for discretely selecting individual pixels, whereas CRT technology employs analog voltage signals to position one or more electron beams on the display surface.
Display processing systems for real-time applications, such as for avionics displays, generally incorporate a hardware vector generation (i.e., line drawing) capability. This hardware provides digital outputs for selecting X (horizontal) and Y (vertical) display screen locations, and digital video to specify the selected intensity and/or color. A separate video on/off output may also be provided. For a calligraphic/stroke type of CRT display, the X, Y, and video signals are converted to analog to directly control the position and intensity of the CRT electron beam(s). The symbol generator hardware then directly refreshes the display by executing its commands at a rate of approximately 60 HZ. For a dynamic display format, the command-list/program should be updated at a rate that is high enough to achieve smooth motion of the symbology. This may require an update rate of 20 or 30 HZ.
For LCD technologyxe2x80x94or for a raster type of CRT-based displayxe2x80x94the display screen is refreshed from a 2-dimensional frame buffer memory, or xe2x80x9cimage memoryxe2x80x9d. An image memory can be an exact 2-D mapping of the pixels of the display screen, whereby each memory location holds a code that determines the color/intensity of its corresponding pixel. The digital X and Y outputs of the symbol generator are then used to address the 2-D image memory. Vectors are written/drawn into image memory instead of directly on the display screen. For real-time applications, a symbol generator is used to update the display format in one image memory while another image memory, which contains the previous update, is simultaneously used to refresh the display screen. Some CRT-based displays are designed to alternate between stroke and raster in a hybrid mode in order to overlay stroke symbology onto raster video.
Avionics display systems often employ separate physical units for the display function and the symbol generator/processor function. Stroke and hybrid CRT displays may utilize an analog interface between the symbol generator and the display unit. If such CRT-based displays are replaced with newer LCD-based units, it may be cost prohibitive to also replace the symbol generator. The new LCD-based display unit should then be designed to function with the existing analog interface. But because LCD technology employs a discrete type of pixel addressing mechanism, this tends to diminish the quality of the displayed symbology.
A conventional approach to the design of a LCD-based display unit with stroke-type analog inputs is to essentially mimic, or simulate, the operation of a CRT-based display. The analog X and Y deflection inputs are converted to digital and used to address a 2-D image memory where the digital/digitized video is written. Thus, the stroke inputs are used to write symbology into an image memory instead of directly onto a CRT display screen. This image memory is then subsequently scanned and read to provide the video for refreshing a LCD screen. While the digitized inputs are used to write into one image memory, a second memory (which stores the prior update) is used to refresh the display. With this design approach, the analog interface contributes errors/anomalies to the displayed image. These result from: 1) induced electromagnetic interference (EMI) on the analog X and Y signalsxe2x80x94from external and internal sources; 2) wideband thermal noise generated within the analog circuitry; 3) phase noise in the sampling operation; and 4) quantization noise from the analog to digital (A-to-D) conversion.
All of these noise sources tend to degrade the quality of the displayed symbology. The severity of EMI depends on the individual application. A low-pass pre-filter is preferably employed before the sampling A-to-D conversion operation to prevent high-frequency EMI from aliasing into the bandwidth of interest, but lower frequency EMI will degrade the quality of the displayed symbology. Thermal noise causes small random deviationsxe2x80x94that exhibit a Gaussian distribution around the normxe2x80x94in the digitized samples of the analog deflection inputs. The effect of thermal noise can be minimized by oversampling the inputs (i.e., sampling at a higher rate than is required by downstream operations) and then employing a low-pass digital filter. Phase noise results from jitter in the sampling time, which can occur within the A-to-D converter circuit and also from jitter in the sampling clock. But in this application, a more significant error can result from an inconsistent phase of the sampling clock relative to the clock in the symbol generator (i.e., on different updates of the display format). The display anomalies that result from quantization noise can be minimized by employing a high resolution A-to-D converter (e.g., a 12-bit converter may provide a significantly higher resolution than the pixel resolution of the display).
Display anomalies can be categorized as either static or dynamic. A noise or distortion that is the same on every display update would be categorized as static. Its location would be fixed relative to either the display screen or to a symbol on the display screen (i.e., where the symbol itself might be in motion). An example of a static anomaly would be the distortions to individual symbols that result from aggressive low-pass filtering of the deflection inputs (e.g., resulting in symbols with severely rounded corners). A dynamic anomaly can be a noise or distortion that moves across the screen and/or through the symbology. It can also be located at a specific screen or specific symbol location and be exhibited on either a periodic or random basis. Since humans are adept at detecting motion/change, dynamic anomalies can be more objectionable than static ones. Increasing the amount of low-pass filtering can reduce the dynamic anomalies that result from EMI. However, this would increase the level of static distortion for the symbology.
Because this conventional design approach to a LCD-based caligraphic display with analog inputs results in objectionable display anomalies, it would be beneficial to employ some other design approach that does not have this problem.
The following summary of the invention is provided to facilitate an understanding of some of the innovative features unique to the present invention, and is not intended to be a full description. Although the present invention has numerous applications, this summary will focus on the caligraphic display application. A full appreciation of the various aspects of the invention can be gained by taking the entire specification, claims, drawings, and abstract as a whole.
The present invention provides a pattern recognition solution that can be implemented using semiconductor memory devices. Memory chips are very high-volume commodity parts that are available at very low cost. Moreover, the density of memory chips (i.e., the number of bits in a single integrated circuit) has increased dramatically with advances in semiconductor technology, and will probably continue to do so. Thus, the invention provides a solution to the pattern recognition problem that achieves a very high level of performance at relatively low cost.
The present invention provides an alternate approach to the design of a LCD-based caligraphic display unit that improves the quality of the displayed symbology. In this alternate approach, the digitized samples of the analog deflection inputs, along with the video input(s), are monitored for the purpose of recognizing the individual symbols that are to be displayed. These symbols can then be regenerated within the display unit using completely digital means, thereby avoiding any degradation in the displayed symbology from the noise and the low-pass filtering at the analog interface. This approach requires a mechanism for reliably recognizing the individual display symbols from the analog deflection and video input(s) to the display unit, even when noise is present on these inputs. Since the symbol recognition function operates in real-time with the inputs to the display unit, the present invention is preferably implemented via hardware for this application, rather than via software. The need for real-time performance would also seem to require a solution that compares the display inputs on a simultaneous basis to the expected inputs for any one of the symbols in a symbol library (i.e., rather than a sequential comparison to one library symbol at a time). The subject invention is a low-cost solution to the symbol/pattern recognition problem that can meet the demanding requirements of this real-time application.
One embodiment of the present invention implements the pattern recognition function by means of a state machine that employs a sequence of table-look-up operations that are designed to recognize patterns in a sequence of inputs. The patterns that are to be recognized (i.e., the library of patterns) are used in deriving the data stored in the memory tables that are used by the table-look-up operations. The tables are organized in a hierarchical, or tree-like, structure having a unique set of memory tables for each level of this structure. The input to this pattern recognition mechanism comprises a time-sequence of memory addresses, which may be derived from the time-sampled and digitized values of one or more analog input signals. This would be the case for the application of a LCD-based calligraphic display unit having analog X and Y inputs. Other applications could derive this sequence of memory addresses by different means.
For the LCD-based calligraphic display, the X and Y input values are normally constant for some time period before the rendering of each display symbol (i.e., except for small changes due to noise). This was required by the older CRT-based display units to allow stabilization of their analog deflection amplifiers. This condition can be detected and used to reset the symbol recognition mechanism before a new display symbol is rendered. In addition, the digitized X and Y inputs can be filtered/averaged during this interval. These filtered values, which are saved, provide an accurate display-screen location for the symbol that is to be rendered.
Not all of the digitized X, Y, and video input samples are required to be used in generating the time-sequence of memory addresses for the symbol recognition mechanism. For example, one algorithm for generating these addresses uses all of the input samples in which the video input changes state and a selected number of the input samples in the intervals between these changes in the video input. For each of these samples, the associated memory address can then be derived by a concatenation of 1) a value representative of the video state just prior to the sample; 2) the relative value of the sampled X input; and 3) the relative value of the sampled Y input. Recall that the X and Y display-screen location prior to the rendering of a symbol is saved. A relative X positionxe2x80x94for each of the X input samplesxe2x80x94can then be derived by subtracting the saved X symbol position from the X value of the input sample. The relative Y values can be derived similarly. Accordingly, the selected input samples are then used to generate a corresponding time-sequence of memory addresses. This sequence of memory addresses is then used as the input to the symbol recognition operation.
The first memory address in the sequence is used to address a single memory table that resides at the first level in the hierarchy of memory tables. If the value of this addressxe2x80x94and hence the values of the inputs for the sample that it representsxe2x80x94is consistent with the rendering of one or more of the symbols in the library, then the output from this address of the memory table points to a specific level-2 table that allows for the possible recognition of the consistent symbol(s). Then the next memory address in the sequence will be used to address this specified table at the second level in the hierarchy. As this process continues, the sequence of input samplesxe2x80x94by means of their associated memory addressesxe2x80x94directs the path through the structure of memory tables until either a symbol is recognized or until it is determined that the input sequence is inconsistent with any of the library symbols.
Three types of outputs are possible for the memory tables. When a completed input sequence is unambiguously recognized as correlating to one of the symbols in the library, the code for that symbol is output from the memory. When an incomplete input sequence isxe2x80x94up to that point in the sequencexe2x80x94consistent with one or more of the library symbols, the memory output points to a specific table at the next level in the hierarchy that will test the next sample of the input sequence against this possibility. And when a given input sample, at any point in an input sequence, establishes that the input sequence is not consistent with any of the library symbols, the output of the memory table indicates this condition. When an input sequence is determined to be inconsistent with any library symbol, the digitized input samples can be used to directly render the symbol into the image memory (i.e., effectively bypassing the symbol regeneration mechanism). But to eliminate the possibility of generating dynamic display anomalies, the symbol recognition mechanism needs to reliably and consistently recognize all of the library symbols (i.e., even when noise is present on the inputs). This requires that the tables be designed to allow for the variations in the values of the input samples that can be encountered under the worst-case noise conditions.
The novel features of the present invention will become apparent to those of skill in the art upon examination of the following detailed description of the invention or can be learned by practice of the present invention. It should be understood, however, that the detailed description of the invention and the specific examples presented, while indicating certain embodiments of the present invention, are provided for illustration purposes only because various changes and modifications within the spirit and scope of the invention will become apparent to those of skill in the art from the detailed description of the invention and claims that follow.